---
title: "递增三元组"
created: 2025-11-28
tags:
  - 算法
---

# 递增三元组

## 题目 [递增三元组](https://www.acwing.com/problem/content/1238/)

![[image-14d5229f.png]]

## 思路分析

暴力三重循环 过7/13

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int a[N],b[N],c[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>a[i];
    for(int i=1;i<=n;i++)  cin>>b[i];
    for(int i=1;i<=n;i++)  cin>>c[i];

    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(c[k]>b[j] && b[j]>a[i])
                    cnt++;
            }
        }
    }
    cout<<cnt;
    return 0;
}
```

![[image-65a9ef0a.png]]

![[image-6e673307.png]]

发现总数量和大于它的数量有关

比如b中比a中2大的有3 4 8 （3个） c中比b中3大的有5 7 9（3个） 比4大的有5 7 9（3个） 比8大的有9（1个） 那么数量好像有点关系
如果比8大的也有3个的话 就可以是3\*3+3\*3+3\*3=27个

看a是不太方便的 但可以确定的是 这里是有点关系的

那从中间的b入手

a中比b中3小的有2（1个） c中比3大的有5 7 9（3个） 那么包含3的选项有1\*3=3个

a中比b中4小的有2（1个） c中比4大的有5 7 9（3个） 那么包含4的选项有1\*3=3个

a中比b中8小的有2 5 6（3个） c中比8大的有9（1个） 那么包含8的选项有3\*1=3个

应该是3+3+3=9个

验算一下 235 237 239 245 247 249 289 589 689确实是9个

那么问题就可以转化成

先把各个序列排序 对于每个b 找到比他小的a有几个（cnt1） 比他大的c有几个（cnt2） 经过这个b的方案就是cnt1\*cnt2 最后累加各个b的方案数即可

在俩序列里做匹配 嗯 二分或者双指针

二分

![[image-bd11fa2e.png]]

双指针

![[image-c4a27beb.png]]

考试时不能调试 要考虑到所有情况确实是有些难度 很多边界问题都是依赖数据报错才发现的 唉

递增三元组

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

LL a[N],b[N],c[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)  cin>>a[i];

    for(int i=1;i<=n;i++)  cin>>b[i];

    for(int i=1;i<=n;i++)  cin>>c[i];

    sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);

    LL cnt=0;

    for(int i=1;i<=n;i++){

        int l=0,r=n;

        while(l<r){

            int mid=l+r+1>>1;

            if(a[mid]<b[i])

                l=mid;

            else

                r=mid-1;

        }

        LL cnta=r;

        l=1,r=n+1;

        while(l<r){

            int mid=l+r>>1;

            if(c[mid]>b[i])

                r=mid;

            else

                l=mid+1;

        }

        LL cntc=n-r+1;

        cnt+=cnta*cntc;

    }

    cout<<cnt;

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

LL a[N],b[N],c[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)  cin>>a[i];

    for(int i=1;i<=n;i++)  cin>>b[i];

    for(int i=1;i<=n;i++)  cin>>c[i];

    sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);

    LL cnt=0;

    LL idx_a=0,idx_c=0;

    for(int i=1;i<=n;i++){

        while(a[idx_a+1]<b[i] && idx_a+1<=n)

            idx_a++;

        LL cntcur_a=idx_a;

        while(c[idx_c+1]<=b[i] && idx_c+1<=n)

            idx_c++;

        LL cntcur_c=n-idx_c;

        cnt+=cntcur_a*cntcur_c;

    }

    cout<<cnt;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[逆行|逆行]] 🏠 [[00-刷题理模型]] ➡️ [[错误票据|错误票据]]